package code;

import java.util.ArrayList;
import java.util.List;

/*
 * 树链剖分的例子
 * 问题描述，在一棵树中，一开始以1号节点为根节点，1号节点被染成黑色。其余的节点都是白色。
 * 有两种操作，一种是将x结点染成黑色，第二种是询问离x节点最近的黑色节点多远
 * 
 */
public class TreeChainCut {

	public TreeChainCut(){
		
	}
	
	class SegTreeNode{
		int l;
		int r;
		int lmin;
		int rmin;
	}
	/*
	 * 树中节点的个数
	 * 树中的边
	 */
	private int n;
	private List<Integer>[] edges;
	private final int INF=1000000000;
	
	/*
	 * size[x]--表x子树中的节点的个数
	 * son[x] --x的重儿子
	 * top[x] --x的所在链的根节点
	 * parent[x]--x的父节点
	 * idx[x] --x节点映射到线段树中的位置
	 * treeIdx[x]--x属于的线段树的索引
	 * len[x] --下标为x的线段树长度
	 */
	
	private int[] size;
	private int[] son;
	private int[] top;
	private int[] parent;
	private int[] idx;
	private int[] treeIdx;
	private int[] len;
	/*
	 * treeCnt树的下标计数
	 * idxCnt结点的下标计数
	 */
	
	private int treeCnt;
	private int idxCnt;
	
	public void init(){
		n=12;
		edges=new ArrayList[n+1];
		for(int i=0;i<=n;i++){
			edges[i]=new ArrayList<Integer>();
		}
		edges[1].add(2);
		edges[1].add(3);
		edges[2].add(4);
		edges[3].add(5);
		edges[5].add(6);
		edges[5].add(7);
		edges[6].add(8);
		edges[6].add(9);
		edges[8].add(11);
		edges[7].add(10);
		edges[10].add(12);
		
		size=new int[n+1];
		son=new int[n+1];
		top=new int[n+1];
		parent=new int[n+1];
		idx=new int[n+1];
		treeIdx=new int[n+1];
		len=new int[n+1];
		treeCnt=0;
	}
	
	/*
	 * 先求size[u],son[u],parent[u]
	 */
	public void dfsI(int u){
		size[u]++;
		int maxSon=0;
		for(int i=0;i<edges[u].size();i++){
			int v=edges[u].get(i);
			dfsI(v);
			size[u]+=size[v];
			parent[v]=u;
			if(maxSon<size[v]){
				maxSon=size[v];
				son[u]=v;
			}
		}
	}
	
	/*
	 * 计算top[u],treeIdx[u],idx[u],len[u]
	 */
	
	public void dfsII(int u,int topV,int step){
		top[u]=topV;
		if(u==top[u]){
			/*
			 * 链的头部
			 */
			treeIdx[u]=treeCnt++;
		}
		idx[u]=step;
		/*
		 * 记录这个线段树中的元素个数
		 */
		len[treeIdx[u]]++;
		for(int i=0;i<edges[u].size();i++){
			int v=edges[u].get(i);
			/*
			 * 重儿子,将其连在u的后面
			 */
			if(v==son[u]){
				dfsII(v,topV,step+1);
			}
			else{
				/*
				 * 新链，需要建树
				 */
				dfsII(v,v,1);
			}
		}
	}
	
	/*
	 * 建treeIdx个线段树
	 */
	List<SegTreeNode[]> segTreeList=new ArrayList<SegTreeNode[]>();
	
	/*
	 * 有[1,n]的结点的节点的线段树，需要3*n的空间来保存整个树的节点
	 */
	public void initSegTrees(){
		for(int i=0;i<treeCnt;i++){
			SegTreeNode[] segTree=new SegTreeNode[3*(len[i]+1)]; 
			segTreeList.add(segTree);
			for(int j=0;j<=len[i];j++)
				segTree[j]=new SegTreeNode();
			buildSegTree(i,1,1,len[i]);
		}
	}
	/*
	 * tIdx表示树的索引，而idx表示树内的区间的下标
	 */
	public void buildSegTree(int tIdx,int idx,int l,int r){
		segTreeList.get(tIdx)[idx].l=l;
		segTreeList.get(tIdx)[idx].r=r;
		segTreeList.get(tIdx)[idx].lmin=INF;
		segTreeList.get(tIdx)[idx].rmin=INF;
		int mid=l+r>>1;
		if(r>l){
			buildSegTree(tIdx,2*idx,l,mid);
			buildSegTree(tIdx,2*idx+1,mid+1,r);
		}
	}
	/*
	 * 将x节点染成黑色，插入结点x,更新x影响的所有父链
	 */
	private int root=1;
	
	public void ColorV(int u){
		int value=0;
		parent[root]=root;
		while(u!=root){
			update(treeIdx[top[u]],1,idx[u],value);
			value=segTreeList.get(treeIdx[top[u]])[1].lmin+1;
			u=parent[top[u]];
		}
	}
	/*
	 * 线段树中单点插入
	 */
	public void update(int tIdx,int idx,int u,int val){
		int l=segTreeList.get(tIdx)[idx].l;
		int r=segTreeList.get(tIdx)[idx].r;
		int mid=l+r>>1;
		if(l==u && r==u){
			if(segTreeList.get(tIdx)[idx].lmin>val){
				segTreeList.get(tIdx)[idx].lmin=val;
				segTreeList.get(tIdx)[idx].rmin=val;
			}
			return ;
		}
		if(mid>=u)
			update(tIdx,2*idx,u,val);
		else update(tIdx,2*idx+1,u,val);
		/*
		 * 更新值
		 */
		if(segTreeList.get(tIdx)[idx].lmin>segTreeList.get(tIdx)[2*idx].lmin)
			segTreeList.get(tIdx)[idx].lmin=segTreeList.get(tIdx)[2*idx].lmin;
		if(segTreeList.get(tIdx)[idx].rmin>segTreeList.get(tIdx)[2*idx+1].rmin)
			segTreeList.get(tIdx)[idx].rmin=segTreeList.get(tIdx)[2*idx+1].rmin;
		if(segTreeList.get(tIdx)[idx].lmin==INF){
			segTreeList.get(tIdx)[idx].lmin=segTreeList.get(tIdx)[2*idx+1].lmin+
					segTreeList.get(tIdx)[2*idx].r-segTreeList.get(tIdx)[2*idx].l+1;
		}
		if(segTreeList.get(tIdx)[idx].rmin==INF){
			segTreeList.get(tIdx)[idx].rmin=segTreeList.get(tIdx)[2*idx].rmin+
					segTreeList.get(tIdx)[2*idx+1].r-segTreeList.get(tIdx)[2*idx+1].l+1;
		}
	}
	/*
	 * 查询u节点，最近的黑色节点多远
	 */
	
	public void QueryV(int u){
		/*
		 * 一种是来自u子树中的黑点，另外一种是来自祖先链中的黑色节点
		 */
	}
	public static void main(String[] args){
		
	}
}
